

//  过桥    bfs遍历最短路径 类似于层序往下走  
//  思路二  转化成为类似动态规划的解法  
//  二维dp   i - j 表示 i - j的步数  
#include <iostream>

using namespace std;
const int N = 2010;
int n;
int arr[N];
int bfs()
{
	int left = 1, right = 1;
	int ret = 0;
	while (left <= right)
	{
		ret++;
		int r = right;
		for (int i = left; i <= right; i++)
		{
			r = max(r, arr[i] + i);
			if (r >= n)
			{
				return ret;
			}
		}
		left = right + 1;
		right = r;
	}
	return -1;
}
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> arr[i];

	cout << bfs() << endl;

	return 0;
}




//  最长公共子序列   nlogn时间复杂度  
int main()
{
    int n, m;
    cin >> n >> m;
    char s1[1010], s2[1010];
    for (int i = 1; i <= n; i++)cin >> s1[i];
    for (int j = 1; j <= m; j++)cin >> s2[j];
    vector<vector<int>>dp(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

//   约瑟夫环 
//   状态转移方程  i 表示当为i个人时 赢的人的编号
//   dp[i] = (dp[i - 1] + m) % i;
class Solution
{
public:
    int LastRemaining_Solution(int n, int m)
    {
        int ans = 0;
        for (int i = 2; i <= n; i++)
        {
            ans = (ans + m) % i;
        }
        return ans;
    }
};



      
//  动态规划解法

class Solution
{
public:
    int lengthOfLIS(vector<int>& nums)
    {
        int n = nums.size();
        int ans = 0;
        vector<int> dp(n, 1);
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = i + 1; j < n; j++)
            {
                if (nums[j] > nums[i])
                {
                    dp[i] = max(dp[i], dp[j] + 1);   // 状态转移方程 
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};


//  猜数字  
//  记忆化搜索   
//  dfs   1-n 每一个数字开头的情况  找出最小值
//  递归左右区间 找左右区间的最大花费  
class Solution
{
    int memo[201][201];  //  记忆表  
public:
    int getMoneyAmount(int n)
    {
        return dfs(1, n);
    }
    int dfs(int left, int right)
    {
        if (left >= right) return 0;
        if (memo[left][right]) return memo[left][right];//  查表  有就直接返回 

        int ret = INT_MAX;
        for (int i = left; i <= right; i++)
        {
            int x = dfs(left, i - 1);   //  左边费用
            int y = dfs(i + 1, right);  //   右边费用
            ret = min(ret, i + max(x, y));   //  当前 i + 左右区间的最大费用  取1-n所有节点开始的最小花费
        }
        return memo[left][right] = ret;
    }
};

//  最长递增路径  
//  记忆化搜索  递归每一个点  每次都记录遍历过的路径长度
//  每次遍历之前查表  有表直接返回 
class Solution
{
    int dx[4] = { 1, -1, 0, 0 };
    int dy[4] = { 0, 0, 1, -1 }; // 辅助数组 
    int n, m;
    int memo[201][201];  // 记忆表
public:
    int longestIncreasingPath(vector<vector<int>>& matrix)
    {
        n = matrix.size(), m = matrix[0].size();
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                ans = max(dfs(matrix, i, j), ans);  // 对每一个结点递归  找最长
            }
        }
        return ans;
    }
    int dfs(vector<vector<int>>& matrix, int i, int j)
    {
        if (memo[i][j]) return memo[i][j];  //  有表直接返回 
        int ret = 1;
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x >= 0 && x < n && y >= 0 && y < m && matrix[x][y] > matrix[i][j])
            {
                ret = max(ret, dfs(matrix, x, y) + 1);   // 找当前节点递归的最长路径长度  
            }
        }
        return memo[i][j] = ret;  //  每次结果都入表 
    }
};    





// 被围绕的区域
// 本题正着去遍历去递归是比较难处理的
// 可以对四条边进行dfs深搜  把搜到的海洋都标记起来
//  剩下的就是 被围绕的区域
class Solution
{
    int dx[4] = { 1, -1, 0, 0 };
    int dy[4] = { 0, 0, 1, -1 };
    int n, m;
    bool vis[201][201];
public:
    void solve(vector<vector<char>>& board)
    {
        n = board.size(), m = board[0].size();
        for (int i = 0; i < n; i++)    //  遍历四条边的  o
        {
            if (board[i][0] == 'O') dfs(board, i, 0);
            if (board[i][m - 1] == 'O') dfs(board, i, m - 1);
        }
        for (int i = 0; i < m; i++)
        {
            if (board[0][i] == 'O') dfs(board, 0, i);
            if (board[n - 1][i] == 'O') dfs(board, n - 1, i);
        }

        for (int i = 1; i < n - 1; i++)  //  最后更新结果  把未标记的 o 改为 x
        {
            for (int j = 1; j < m - 1; j++)
            {
                if (board[i][j] == 'O' && !vis[i][j])
                {
                    board[i][j] = 'X';
                }
            }
        }
    }
    void dfs(vector<vector<char>>& board, int i, int j)
    {
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x < n && x >= 0 && y < m && y >= 0 && board[x][y] == 'O' && !vis[x][y]) // 递归条件
            {
                vis[x][y] = 1;  // 满足条件就标记  
                dfs(board, x, y);
            }
        }
    }
};

//  bfs解法
//  还是相同的思路  和前面几个题目都类似的
class Solution
{
    int dx[4] = { 1, -1, 0, 0 };
    int dy[4] = { 0, 0, 1, -1 };
    int n, m;
    bool vis[201][201];
public:
    void solve(vector<vector<char>>& board)
    {
        n = board.size(), m = board[0].size();
        for (int i = 0; i < n; i++)   // 正常遍历四条边  进行bfs搜索
        {
            if (board[i][0] == 'O') bfs(board, i, 0);
            if (board[i][m - 1] == 'O') bfs(board, i, m - 1);
        }
        for (int i = 0; i < m; i++)
        {
            if (board[0][i] == 'O') bfs(board, 0, i);
            if (board[n - 1][i] == 'O') bfs(board, n - 1, i);
        }

        for (int i = 1; i < n - 1; i++)
        {
            for (int j = 1; j < m - 1; j++)
            {
                if (board[i][j] == 'O' && !vis[i][j])
                {
                    board[i][j] = 'X';
                }
            }
        }
    }
    void bfs(vector<vector<char>>& board, int i, int j)
    {
        vis[i][j] = 1;
        queue<pair<int, int>> q;
        q.push({ i, j });
        while (q.size())
        {
            i = q.front().first, j = q.front().second;
            q.pop();
            for (int k = 0; k < 4; k++)
            {
                int x = i + dx[k];
                int y = j + dy[k];
                if (x < n && x >= 0 && y < m && y >= 0 && board[x][y] == 'O' && !vis[x][y])  // 判断条件
                {
                    vis[x][y] = 1;   // 满足条件 标记 
                    q.push({ x, y }); // 入队列
                }
            }

        }
    }
};		